1. Field
The present embodiments relate to cryptographic techniques for constructing a blockcipher-based encryption scheme. More specifically, the present embodiments relate to techniques for constructing fast and provably secure schemes for deterministically enciphering data from a small domain, like credit card numbers, using a conventional block cipher.
2. Related Art
Imagine wanting to encrypt a nine-decimal-digit plaintext, such as a U.S. Social Security number, into a ciphertext that is also a nine-decimal-digit number. This operation is useful for storing the ciphertext in the same record structure as the plaintext. Modern cryptographic techniques typically assume the plaintext input to a block cipher has a block size of 128 bits and that the block cipher outputs a ciphertext of 128 bits. Unfortunately, nine-decimal-digit plaintext input and nine-decimal-digit ciphertext output are incompatible with a block size of 128 bits.
One could imagine attempting to construct the desired scheme directly, by modifying a known primitive, but such constructions have many shortcomings. For example, one could modify the definition of the Advanced Encryption Standard (AES) so that it would take in a nine-decimal-digit plaintext and output a ciphertext that is also a nine-decimal-digit number. But both the specification and implementations of AES have been carefully crafted, and the specification has been in the public domain for a considerable time, so a modified version of AES would need careful study by many cryptographers to determine whether the level of security believed to be provided by AES was compromised. As such, it is neither feasible nor desirable to employ such an approach.
In an alternative approach, rather than modifying AES, one could embed the nine-decimal-digit plaintext one wants to encrypt into a 128-bit string, and then invoke AES. Because AES returns a 128-bit string, the output would have to be mapped back into a nine-decimal-digit number. But it is impossible to encode a 128-bit string into nine decimal digits, since 2128>109.
Is it really a problem if one cannot encrypt nine-decimal-digit numbers into nine-decimal-digit numbers? Consider a database of U.S. Social Security numbers. Suppose one wished to silently replace all of the Social Security numbers with encrypted Social Security numbers. Using AES to produce an output of 128 bits and using this in place of the nine-decimal-digit numbers would break existing applications that access and manipulate U.S. Social Security numbers, because such applications, expecting nine-decimal-digit strings, are now faced with 128-bit binary strings instead. Further, the database schema for each table containing U.S. Social Security numbers would need to be changed to support a different data type, and dependent applications would need to be modified accordingly. Conventional block ciphers like AES are, therefore, not directly usable to encrypt on small domains of practical interest, because these techniques send 128-bit inputs to 128-bit outputs.
Hence, what is needed is a cryptographic technique to encipher elements from a small domain into elements of the same small domain.